package algorithm.sorty.sort;

import algorithm.sorty.Sort;
import datastructure.map.model.Person;

/**
 * @Description: 计数排序 复杂度O(n)
 * @Author Ammar
 * @Create 2023/5/5 07:00
 */
public class CountingSort extends Sort<Integer> {
    @Override
    public void sort() {
        // 找出最大值
        int max = array[0];
        int min = array[0];
        for (Integer integer : array) {
            if (integer > max) {
                max = integer;
            }
            if (integer < min) {
                min = integer;
            }
        }

        // 开辟内存空间，存储每个整数出现的累加次数
        int[] counts = new int[max - min + 1];
        // 统计每个整数出现的次数
        for (int i = 0; i < array.length; i++) {
            counts[array[i] - min]++;
        }

        // 累加次数
        for (int i = 1; i < counts.length; i++) {
            counts[i] += counts[i - 1];
        }

        // 从后往前遍历元素，将它放到有序数组中的合适位置
        int[] newArray = new int[array.length];

        // 从后往前遍历，保证稳定性
        for (int i = array.length - 1; i >= 0; i--) {
            newArray[--counts[array[i] - min]] = array[i];
        }
    }

    // 计数排序优化前
    public void sort1() {
        // 找出最大值
        int max = array[0];
        for (Integer integer : array) {
            if (integer > max) {
                max = integer;
            }
        }

        // 开辟内存空间，存储每个整数出现的次数
        int[] counts = new int[max + 1];
        for (Integer integer : array) {
            counts[integer]++;
        }

        // 根据整数的出现次数，对整数进行排序
        int index = 0;
        for (int i = 0; i < counts.length; i++) {
            while (counts[i]-- > 0) {
                array[index++] = i;
            }
        }
    }

    public void sort2(Person[] persions) {
        // 找出最大值
        int max = persions[0].age;
        int min = persions[0].age;
        for (Person person : persions) {
            if (person.age > max) {
                max = person.age;
            }
            if (person.age < min) {
                min = person.age;
            }
        }

        // 开辟内存空间，存储每个整数出现的累加次数
        int[] counts = new int[max - min + 1];
        // 统计每个整数出现的次数
        for (int i = 0; i < persions.length; i++) {
            counts[persions[i].age - min]++;
        }

        // 累加次数
        for (int i = 1; i < counts.length; i++) {
            counts[i] += counts[i - 1];
        }

        // 从后往前遍历元素，将它放到有序数组中的合适位置
        Person[] newArray = new Person[persions.length];

        // 从后往前遍历，保证稳定性
        for (int i = persions.length - 1; i >= 0; i--) {
            newArray[--counts[persions[i].age - min]] = persions[i];
        }
    }
}
